//动态区间第k小（整体二分）：(ranking)
//比线段树套treap快5倍,比动态主席树快10倍
type
    query=record
        x,y,k,s,opt,cur:longint;
    end;
var
    ch:char;
    i,m,n,num,cnt,x,y,z:longint;
    q,q1,q2:array[0..100100]of query;
    a,ans,tmp,t:array[0..100100]of longint;

function lowbit(x:longint):longint;
begin
    exit(x and (-x));
end;

procedure add(x,y:longint);
begin
    while x<=n do
        begin inc(t[x],y); inc(x,lowbit(x)); end;
end;

function ask(x:longint):longint;
var k:longint=0;
begin
    while x>0 do
        begin inc(k,t[x]); dec(x,lowbit(x)); end;
    exit(k);
end;

procedure divide(head,tail,l,r:longint);
var i,mid,l1,l2:longint;
begin
    if head>tail then exit;
    if l=r then
        begin
            for i:=head to tail do
                if q[i].opt=3 then ans[q[i].s]:=l;
            exit;
        end;
    mid:=(l+r)>>1;
    for i:=head to tail do
        begin
            if (q[i].opt=1)and(q[i].y<=mid) then add(q[i].x,1);
            if (q[i].opt=2)and(q[i].y<=mid) then add(q[i].x,-1);
            if q[i].opt=3 then tmp[i]:=ask(q[i].y)-ask(q[i].x-1);
        end;
    for i:=head to tail do
        begin
            if (q[i].opt=1)and(q[i].y<=mid) then add(q[i].x,-1);
            if (q[i].opt=2)and(q[i].y<=mid) then add(q[i].x,1);
        end;
    l1:=0; l2:=0;
    for i:=head to tail do
        if q[i].opt=3 then
            if q[i].cur+tmp[i]>=q[i].k then
                begin inc(l1); q1[l1]:=q[i]; end
            else
                begin
                    inc(q[i].cur,tmp[i]); inc(l2); q2[l2]:=q[i];
                end
        else
            if q[i].y<=mid then
                begin inc(l1); q1[l1]:=q[i]; end
            else
                begin inc(l2); q2[l2]:=q[i]; end;
    for i:=1 to l1 do q[head+i-1]:=q1[i];
    for i:=1 to l2 do q[head+l1+i-1]:=q2[i];
    divide(head,head+l1-1,l,mid);
    divide(head+l1,tail,mid+1,r);
end;

begin
    assign(input,'ranking.in'); reset(input);
    assign(output,'ranking.out'); rewrite(output);
    readln(n,m); cnt:=0; num:=0;
    for i:=1 to n do
        begin
            read(a[i]); inc(num);
            q[num].x:=i; q[num].y:=a[i];
            q[num].opt:=1; q[num].s:=0;
        end;
    readln;
    for i:=1 to m do
        begin
            read(ch);
            if ch='Q' then
                begin
                    read(ch); readln(x,y,z); inc(num);
                    q[num].x:=x; q[num].y:=y; q[num].k:=z;
                    q[num].opt:=3; inc(cnt); q[num].s:=cnt;
                end
            else
                begin
                    read(ch); readln(x,y); inc(num);
                    q[num].x:=x; q[num].y:=a[x];
                    q[num].opt:=2; q[num].s:=0;
                    inc(num); q[num].x:=x; q[num].y:=y;
                    q[num].opt:=1; q[num].s:=0;
                    a[x]:=y;
                end;
        end;
    divide(1,num,0,1000000000);
    for i:=1 to cnt do writeln(ans[i]);
    close(input); close(output);
end.

//ZJOI2013区间第k大加强版（仅限正数）：(sequence)
//比权值线段树套区间线段树快2倍
type arr=array[0..1,0..50100]of longint;
var
    i,m,n,times:longint;
    a1,a2:arr;
    a,b,c,ans,t,t1,t2,flag:array[0..50100]of longint;

function lowbit(x:longint):longint;
begin
    exit(x and (-x));
end;

function count1(var data:arr; x:longint):longint;
var k:longint=0;
begin
    while x>0 do
        begin
            if data[0,x]=times then inc(k,data[1,x]);
            dec(x,lowbit(x));
        end;
    exit(k);
end;

procedure add1(var data:arr; x,d:longint);
begin
    while x<=n do
        begin
            if data[0,x]=times then inc(data[1,x],d)
            else
                begin data[0,x]:=times; data[1,x]:=d; end;
            inc(x,lowbit(x));
        end;
end;

function count(s,t:longint):longint;
begin
    exit(count1(a1,s)*(t-s+1)+(t+1)*(count1(a1,t)-count1(a1,s))-(count1(a2,t)-count1(a2,s)));
end;

procedure add(s,t,c:longint);
begin
    add1(a1,s,c); add1(a2,s,s*c);
    add1(a1,t+1,-c); add1(a2,t+1,-c*(t+1));
end;

procedure solve(head,tail,l,r:longint);
var tmp,mid,i,k:longint;
begin
    if head>tail then exit;
    if l=r then
        begin
            for i:=head to tail do
                if flag[t[i]]=2 then ans[t[i]]:=l;
            exit;
        end;
    t1[0]:=0; t2[0]:=0; inc(times); mid:=(l+r)>>1;
    for i:=head to tail do
        if flag[t[i]]=1 then
            if c[t[i]]<=mid then
                begin
                    inc(t1[0]); t1[t1[0]]:=t[i];
                    add(a[t[i]],b[t[i]],1);
                end
            else
                begin inc(t2[0]); t2[t2[0]]:=t[i]; end
        else
            begin
                tmp:=count(a[t[i]],b[t[i]]);
                if tmp<c[t[i]] then
                    begin
                        dec(c[t[i]],tmp);
                        inc(t2[0]); t2[t2[0]]:=t[i];
                    end
                else
                    begin inc(t1[0]); t1[t1[0]]:=t[i]; end;
            end;
    k:=t1[0]+head-1;
    for i:=head to k do t[i]:=t1[i-head+1];
    for i:=k+1 to tail do t[i]:=t2[i-k];
    solve(head,k,l,mid); solve(k+1,tail,mid+1,r);
end;

begin
    assign(input,'ranking.in'); reset(input);
    assign(output,'ranking.out'); rewrite(output);
    readln(n,m); times:=0;
    for i:=1 to m do
        begin
            readln(flag[i],a[i],b[i],c[i]);
            if flag[i]=1 then c[i]:=n-c[i]+1;
            t[i]:=i;
        end;
    solve(1,m,1,n);
    for i:=1 to m do
        if flag[i]=2 then writeln(n-ans[i]+1);
    close(input); close(output);
end.